/*************************************************************************
    > File Name: reg2nfa.cpp
    > Author: liujing
    > Mail: jingliu.cs@gmail.com 
    > Created Time: 2014年10月21日 星期二 00时47分49秒
 ************************************************************************/

#include "reg2nfa.h"

RegToNFA::RegToNFA(void):temp(0){
}

RegToNFA::~RegToNFA(void){
}

RegToNFA::RegToNFA(string reg):temp(0){
	this->reg=reg;
}

void RegToNFA::createNFA(){
	int regLen=reg.length();
	int graphLen=2*regLen;
	graph=new Graph(graphLen);

	int i;
	wchar_t ch;
	for(i=0;i<regLen;i++){
		ch=reg[i];
		if(!isOperator(ch)){
			//basic operator
			GraphNode* n1=graph->graphLines[temp++]->graphNode;
			GraphNode* n2=graph->graphLines[temp++]->graphNode;
			basicOperate(n1,n2,i);

			if(i+1<regLen&&(!isOperator(reg[i+1])||reg[i+1]==('('))){
				operatorStack.push('&');
			}
		}else if(isOperator(ch)){
			switch(ch){
				case ('*'):
					if(graphStack.empty()){
						return;
					}
					repeatOperate();
					if(i+1<reg.length()&&(!isOperator(reg[i+1])||reg[i+1]==('('))){
						operatorStack.push('&');
					}
					break;
				case ('+'):
					if(graphStack.empty()){
						return;
					}
					if(!operatorStack.empty()){
						ch=operatorStack.top();
						while(ch!=('(')){
							ch=operatorStack.top();
							ght2=graphStack.top();
							graphStack.pop();
							ght1=graphStack.top();
							graphStack.pop();
							
							switch(ch){
								case ('+'):
									choiceOperate();
									break;
								case ('&'):
									appositeOperate();
									break;
								if(!operatorStack.empty()){
									ch=operatorStack.top();
								}else{
									break;
								}
							}
						}
						operatorStack.push(('+'));
						break;
					}
					operatorStack.push('+');
					break;
				case ('('):
					operatorStack.push('(');
					break;
				case (')'):
					if(graphStack.empty()){
						return;
					}
					ch=operatorStack.top();
					operatorStack.pop();
					while(ch!=('(')){
						ght2=graphStack.top();
						graphStack.pop();
						ght1=graphStack.top();
						graphStack.pop();

						switch(ch){
							case ('&'):
								appositeOperate();
								break;
							case ('+'):
								choiceOperate();
								break;
							}
							ch=operatorStack.top();
							operatorStack.pop();
						}
						if(i+1<regLen&&(!isOperator(reg[i+1])||reg[i+1]==('('))){
							operatorStack.push(('&'));
						}
						break;
					default:
						break;
					
			}
		}
	}

	while(!operatorStack.empty()){
		ch=operatorStack.top();
		operatorStack.pop();
		ght2=graphStack.top();
		graphStack.pop();
		ght1=graphStack.top();
		graphStack.pop();
		switch(ch){
			case ('&'):
				appositeOperate();
				break;
			case ('+'):
				choiceOperate();
				break;
		}
	}
	return;
}

bool RegToNFA::isOperator(wchar_t ch){
	if(ch==('+')||ch==('*')||ch==('(')||ch==(')')){
		return TRUE;
	}
	return FALSE;
}

void RegToNFA::basicOperate(GraphNode* n1,GraphNode* n2,int i){
	graph->start=n1->getID();
	graph->end=n2->getID();
	graph->addEdge(*n1,*n2,reg[i]);
	GraphHeadTail graphHeadTail;
	graphHeadTail.start=graph->start;
	graphHeadTail.end=graph->end;
	graphStack.push(graphHeadTail);
}

void RegToNFA::repeatOperate(){
	GraphHeadTail ght=graphStack.top();
	graphStack.pop();
	GraphNode* n1=graph->graphLines[ght.start]->graphNode;
	GraphNode* n2=graph->graphLines[ght.end]->graphNode;
	GraphNode* n3=graph->graphLines[temp++]->graphNode;
	GraphNode* n4=graph->graphLines[temp++]->graphNode;

	graph->start=n3->getID();
	graph->end=n4->getID();

	graph->addEdge(*n3,*n1,'E');
	graph->addEdge(*n2,*n4,'E');
	graph->addEdge(*n3,*n4,'E');
	graph->addEdge(*n2,*n1,'E');

	GraphHeadTail graphHeadTail;
	graphHeadTail.start=graph->start;
	graphHeadTail.end=graph->end;
	graphStack.push(graphHeadTail);
}

void RegToNFA::choiceOperate(){
	GraphNode* n3=graph->graphLines[temp++]->graphNode;
	GraphNode* n4=graph->graphLines[temp++]->graphNode;

	graph->start=n3->getID();
	graph->end=n4->getID();

	GraphNode* n11=graph->graphLines[ght1.start]->graphNode;
	GraphNode* n12=graph->graphLines[ght1.end]->graphNode;
	GraphNode* n21=graph->graphLines[ght2.start]->graphNode;
	GraphNode* n22=graph->graphLines[ght2.end]->graphNode;

	graph->addEdge(*n3,*n11,'E');
	graph->addEdge(*n3,*n21,'E');
	graph->addEdge(*n12,*n4,'E');
	graph->addEdge(*n22,*n4,'E');

	GraphHeadTail graphHeadTail;
	graphHeadTail.start=graph->start;
	graphHeadTail.end=graph->end;
	graphStack.push(graphHeadTail);
}

void RegToNFA::appositeOperate(){
	GraphNode* n11=graph->graphLines[ght1.start]->graphNode;
	GraphNode* n12=graph->graphLines[ght1.end]->graphNode;
	GraphNode* n21=graph->graphLines[ght2.start]->graphNode;
	GraphNode* n22=graph->graphLines[ght2.end]->graphNode;
	
	graph->start=n11->getID();
	graph->end=n22->getID();

	graph->addEdge(*n12,*n21,'E');
	GraphHeadTail graphHeadTail;
	graphHeadTail.start=graph->start;
	graphHeadTail.end=graph->end;
	graphStack.push(graphHeadTail);
}

void RegToNFA::printGraphLink(void){
	int i,j;
	for(i=0;i<graph->graphLines.size();i++){
		cout<<endl;
		cout<<"ID:"<<graph->graphLines[i]->graphNode->ID;		
		for(j=0;j<graph->graphLines[i]->graphNodes.size();j++){
			cout<<",";
			cout<<"ID:"<<graph->graphLines[i]->graphNodes[j]->graphNode->ID<<graph->graphLines[i]->graphNodes[j]->str;
		}
	}
	cout<<endl;
	cout<<"start:"<<graph->start<<"end:"<<graph->end;
}


bool RegToNFA::isVisited(GraphNode* graphNode){
	int i;
	for(i=0;i<isVisitedGraphNodes.size();i++){
		if(graphNode->ID==isVisitedGraphNodes[i]->ID){
			return true;
		}
	}
	return false;
}

GraphNode* RegToNFA::findGraphNode(int ID){
	int i;
	for(i=0;i<this->isVisitedGraphNodes.size();i++){
		if(ID==isVisitedGraphNodes[i]->ID){
			return isVisitedGraphNodes[i];
		}
	}
	return NULL;
}

